#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Solution:
    def levelOrderBottom(self, root):
        # write your code here
        self.ret = []
        self.rec_dfs_level_order(root, 1)

        return self.ret

    def rec_dfs_level_order(self, node, depth):
        if node is None:
            return

        if len(self.ret) < depth:
            assert len(self.ret) == depth-1
            self.ret.insert(0, [])

        # self.ret[depth-1].append(node.val)
        self.ret[len(self.ret)-depth].append(node.val)
        self.rec_dfs_level_order(node.left, depth+1)
        self.rec_dfs_level_order(node.right, depth+1)


def main():
    print("start main")

if __name__ == "__main__":
    main()
